package datastructure.array;

/**
 * 实现两个有序数组合并为一个有序数组
 *
 * @author hubb
 * @Date 2019/3/28 21:52
 */
public class MergeOrderedArrays {

    public int[] sortAndConnectArray(int[] firstArray, int[] lastArray) {
        int[] returnArray = new int[firstArray.length + lastArray.length];
        //若两个Arr中其中一个Arr的都比另一个大，则能直接合成
        if (firstArray[firstArray.length - 1] < lastArray[0]) {
            returnArray = connectArray(firstArray, lastArray);
            return returnArray;
        }
        if (lastArray[lastArray.length - 1] < firstArray[0]) {
            returnArray = connectArray(lastArray, firstArray);
            return returnArray;
        }
        //取firstArray的第一个元素与lastArray的第一个元素比较
        //小的一方，放入returnArray,并使其索引+1，继续比较，直到最后
        int indexA = 0;
        int indexB = 0;
        int indexC = 0;
        while (indexA <= firstArray.length - 1 || indexB <= lastArray.length - 1) {
            if (firstArray[indexA] < lastArray[indexB]) {
                returnArray[indexC] = firstArray[indexA++];
            } else {
                returnArray[indexC] = lastArray[indexB++];
            }
            //其中一方的数组已经全部遍历，将余下的数组部分写入ResultArr
            //全部遍历完毕则因为IndexOfXX++的原因应该是正好等于Arr.Length
            if (indexA > firstArray.length - 1) {
                returnArray = addArray(returnArray, indexC + 1, lastArray, indexB);
                return returnArray;
            }
            if (indexB > lastArray.length - 1) {
                returnArray = addArray(returnArray, indexC + 1, firstArray, indexA);
                return returnArray;
            }
            indexC++;
        }
        return returnArray;
    }

    private int[] addArray(int[] returnArray, int indexC, int[] addArray, int addIndex) {
        while (addIndex <= addArray.length - 1) {
            returnArray[indexC++] = addArray[addIndex++];
        }
        return returnArray;
    }

    private int[] connectArray(int[] firstArray, int[] lastArray) {
        int[] retrunArray = new int[firstArray.length + lastArray.length];
        for(int i = 0; i < firstArray.length; i++) {
            retrunArray[i] = firstArray[i];
        }
        int j = 0;
        for(int i = firstArray.length; i < retrunArray.length; i++) {
            retrunArray[i] = lastArray[j++];
        }
        return retrunArray;
    }

    public int[] mergeArrays(int[] a, int[] b) {
        int[] result = new int[a.length + b.length];
        int i=0, j=0, k=0;
        while (i < a.length && j < b.length) {
            if(a[i]<b[j]){
                result[k++]=a[i++];
            }else{
                result[k++]=b[j++];
            }
        }
        while(i<a.length){
            result[k++]=a[i++];
        }
        while(j<b.length){
            result[k++]=b[j++];
        }
        return result;
    }

}
